<?php

/**
 * 原理：选出最小的一个数字与第一个位置数字交换，之后再剩余的数当中再次找到最小的数字与第二个位置交换，依此循环到倒数第二个数字和最后一个数字比较结束为止。（每一轮还是只能找出一个最大【小】值）时间复杂度依然那么高
 */
class 选择排序
{
    public function 运行($输入数组)
    {
        $数组长度 = count($输入数组);

        if ($数组长度 <= 1) {
            return $输入数组;
        }

        for ($i = 0; $i < $数组长度 - 1; $i++) { 
            // 初始化最小的下标为第一个
            $最小值下标 = $i;
            for ($j = $i + 1; $j < $数组长度; $j++) { 
                if ($输入数组[$最小值下标] > $输入数组[$j]) {
                    $最小值下标 = $j;
                }
            }
            // 一轮比较完成后，将最小标与i所在位置交换
            if ($最小值下标 != $i) {
                $临时变量 = $输入数组[$最小值下标];
                $输入数组[$最小值下标] = $输入数组[$i];
                $输入数组[$i] = $临时变量;
            }
        }

        return $输入数组;
    }
}

$输入数组 = [5, 9, 6, 3, 1];
$实例 = new 选择排序();

$结果数组 = $实例->运行($输入数组);

print_r($结果数组);